import java.util.*;
public class Solution {
    //JZ56 数组中只出现一次的两个数字
    public int[] FindNumsAppearOnce (int[] array) {
        //利用map
        HashMap<Integer,Integer>map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(map.containsKey(array[i])){
                int val=map.get(array[i]);
                map.put(array[i],val+1);
            }else{
                map.put(array[i],1);
            }
        }
        int [] arr=new int[2];
        int count=0;
        //再次遍历数组
        for(int i=0;i<array.length;i++){
            if(map.get(array[i])==1){
                arr[count++]=array[i];
            }
        }
        Arrays.sort(arr);
        return arr ;

    }
    //JZ55 二叉树的深度
    public int TreeDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftTree =TreeDepth(root.left);
        int rightTree=TreeDepth(root.right);
        return leftTree>rightTree?leftTree+1:rightTree+1;

    }
    //JZ54 二叉搜索树的第k个节点
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    private TreeNode cur=null;
    protected int count=0;
    protected void inorder(TreeNode root,int k){
        if(root==null||count>k){
            return;
        }
        inorder(root.left,k);
        count++;
        if(count==k){
            cur=root;
            return;
        }
        inorder(root.right,k);
    }
    public int KthNode (TreeNode proot, int k) {
        //二叉搜索树的中序遍历是有序的
        inorder(proot,k);
        if(cur!=null){
            return cur.val;
        }
        return  -1;
    }
}
    //JZ52 两个链表的第一个公共结点
    class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    //记录phead1的个数，pHead2的个数
     Queue<ListNode>q1=new LinkedList<>();
    Queue<ListNode>q2=new LinkedList<>();
    int count1=0,count2=0;//记录个数
    while(pHead1!=null){
      q1.offer(pHead1);
      count1++;
      pHead1=pHead1.next;
    }
    while(pHead2!=null){
        q2.offer(pHead2);
        count2++;
        pHead2=pHead2.next;
    }
    if(count1>count2){
        int len=count1-count2;
        while(len>0){
            q1.poll();
            len--;
        }
    }else{
        int len=count2-count1;
        while(len>0){
            q2.poll();
            len--;
        }
    }
    while(q1.peek()!=q2.peek()){
        q1.poll();
        q2.poll();
    }
     return q1.peek();
    }
}
